package main.Q101_200;

import java.util.*;

public class Q101_110 {
    public static void main(String[] args) {
        System.out.println("Question101：对称二叉树");
        System.out.println("Question102：二叉树的层序遍历");
        System.out.println("Question103：二叉树的锯齿形层序遍历");
        System.out.println("Question104：二叉树的最大深度");
        System.out.println("Question105：从前序和中序遍历序列构造二叉树");
        System.out.println("Question106：从中序与后序遍历序列构造二叉树");
        System.out.println("Question107：二叉树的层序遍历Ⅱ");
        System.out.println("Question108：将有序数组转换为二叉搜索树");
        System.out.println("Question109：有序链表转换二叉搜索树");
        System.out.println("Question110：平衡二叉树");
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class Question101{
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

class Question102{
    public List<List<Integer>> levelOrder(TreeNode root) {//map中存在同层顺序问题
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}

class Question103{
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            boolean flag=false;
            while (!queue.isEmpty()){
                int size=queue.size();
                List<Integer> tempList=new ArrayList<>();
                for (int i=0;i<size;i++){
                    TreeNode curNode=queue.poll();
                    tempList.add(curNode.val);
                    if (curNode.left!=null) queue.add(curNode.left);
                    if (curNode.right!=null) queue.add(curNode.right);
                }
                if (flag){//偶数层反转
                    Collections.reverse(tempList);
                    list.add(tempList);
                    flag=!flag;
                }else {//奇数层不反转
                    list.add(tempList);
                    flag=!flag;
                }
            }
        }
        return list;
    }
}

class Question104{
    public int maxDepth(TreeNode root) {
        if (root==null) return 0;
        Queue<TreeNode> queue=new LinkedList<>();//队列
        Map<TreeNode,Integer>  map=new HashMap<>();//记录节点的层数
        queue.add(root);
        map.put(root,1);
        int curLevel=1;
        while (!queue.isEmpty()){
            TreeNode curNode=queue.poll();//队首出队
            if (curLevel!=map.get(curNode)){
                curLevel++;
            }
            if (curNode.left!=null) {
                queue.add(curNode.left);
                map.put(curNode.left,curLevel+1);
            }
            if (curNode.right!=null) {
                queue.add(curNode.right);
                map.put(curNode.right,curLevel+1);
            }
        }
        return curLevel;
    }
}

class Question105{
    public int getIndexFromInorder(int[] inorder,int target,int left,int right){
        int index=left;
        while (left<=right){
            if (inorder[left]==target){
                index=left;
                break;
            }
            left++;
        }
        return index;
    }
    public int getStartIndexFromPreorder(int[] pre,int[] in,int inLeft,int inRight){
        int index=Integer.MAX_VALUE;
        for (int i=inLeft;i<=inRight;i++){
            int temp=0;
            for (int j=0;j<pre.length;j++){
                if (in[i]==pre[j]) temp=j;
            }
            if (temp<index) index=temp;
        }
        return index;
    }
    public TreeNode process(int[] pre,int[] in,int inLeft,int inRight,int preLeft){
        if (inLeft>inRight||inRight<inLeft) return null;
        TreeNode curNode=new TreeNode(pre[preLeft]);//该节点的值必定为该段范围内的首元素
        int index=getIndexFromInorder(in,pre[preLeft],inLeft,inRight);//获取该元素在中序序列的下标
        int LeftPreStart=getStartIndexFromPreorder(pre,in,inLeft,index-1);
        int RightPreStart=getStartIndexFromPreorder(pre,in,index+1,inRight);
        curNode.left=process(pre,in,inLeft,index-1,LeftPreStart);//构建左子树
        curNode.right=process(pre,in,index+1,inRight,RightPreStart);//构建右子树
        return curNode;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
//        int left=0,right= preorder.length-1;
//        TreeNode root=process(preorder,inorder,left,right,left);
//        return root;
    }
}

class Question106{
    Map<Integer,Integer> index =new HashMap<>();
    public TreeNode process(int[] inorder, int[] postorder, int il, int ir,int pl, int pr) {
        if(pl > pr ) return null;
        int k = index.get(postorder[pr]); //中序遍历根节点位置
        TreeNode root = new TreeNode(postorder[pr]); //创建根节点
        root.left  = process(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
        root.right = process(inorder, postorder, k + 1, ir, pl + k - 1 - il + 1, pr - 1);
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n=inorder.length;
        for (int i=0;i<inorder.length;i++) index.put(inorder[i], i);
        return process(inorder,postorder,0,n-1,0,n-1);
    }
}

class Question107{
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                List<Integer> tempList=new ArrayList<>();
                for (int i=0;i<size;i++){
                    TreeNode curNode=queue.poll();
                    tempList.add(curNode.val);
                    if (curNode.left!=null) queue.add(curNode.left);
                    if (curNode.right!=null) queue.add(curNode.right);
                }
                list.add(tempList);
            }
        }
        Collections.reverse(list);
        return list;
    }
}

class Question108{
    public TreeNode process(int[] nums,int left,int right){
        if (left>right) return null;
        int index=(left+right+1)/2;
        TreeNode curNode=new TreeNode(nums[index]);
        curNode.left=process(nums,left,index-1);
        curNode.right=process(nums,index+1,right);
        return curNode;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return process(nums,0, nums.length-1);
    }
}

class Question109{
    public Integer[] listToArray(ListNode head){
        List<Integer> list=new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head=head.next;
        }
        Integer[] result=list.toArray(new Integer[0]);
        return result;
    }
    public TreeNode process(Integer[] nums,int left,int right){
        if (left>right) return null;
        int index=(left+right+1)/2;
        TreeNode curNode=new TreeNode(nums[index]);
        curNode.left=process(nums,left,index-1);
        curNode.right=process(nums,index+1,right);
        return curNode;
    }
    public TreeNode sortedListToBST(ListNode head) {
        Integer[] listArray=listToArray(head);
        TreeNode root=process(listArray,0,listArray.length-1);
        return root;
    }
}

class Question110{
    public class InfoType{
        public int height;
        public boolean isBalanced;
        public InfoType(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
    public InfoType process(TreeNode root){
        if (root==null) return new InfoType(0,true);
        InfoType leftData=process(root.left);
        InfoType rightData=process(root.right);
        int height=Math.max(leftData.height, rightData.height)+1;
        boolean flag=false;
        if (leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height- rightData.height)<2) flag=true;
        return new InfoType(height,flag);
    }
    public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }
}